package src.BlueBridge.DeepRecursion;

import java.util.Scanner;

/**
 * 如下图所示，玩家需要根据9X9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行
 * 每一列，每一个同色九宫内的数字均含1-9
 * 数字的答案都是唯一的
 * 格式要求，输入9行，每行9个数字，0代表位置，其他数字为已知
 * 输出九行，每行9表示熟读的解
 *
 */

public class _8数独游戏 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char[][] table = new char[9][];
        for (int i = 0 ; i < 9 ; i++) {
            table[i] = sc.nextLine().toCharArray();
        }
        dfs(table, 0, 0);
    }

    /**
     * 要定从哪个位置开始
     * @param table
     * @param x 横坐标
     * @param y 纵坐标
     */
    public static void dfs(char[][] table, int x, int y) {
        if (x == 9) {
            print(table);
            System.exit(0);
        }
        // 如果当前位置没有数值
        if (table[x][y] == '0') {
            // 选1-9之间合法的数字填到x,y这个位置
            for (int i = 1 ; i <= 9 ; i++) {
                boolean res = check(table, x, y, i);
                if (res) {
                    table[x][y] = (char)('0' + i);
                    // 到下一个状态
                    // 行要不要动取决于y有没有到最后一列
                    dfs(table, x + (y + 1) / 9, (y + 1) % 9);
                    // 回溯
                    table[x][y] = '0';
                }
            }
        }else {// 否则，有数值
            // 继续找下一个需要处理的位置
            dfs(table, x + (y + 1) / 9, (y + 1) % 9);
        }
    }

    public static void print(char[][] table) {
        for (int i = 0 ; i < 9 ; i++) {
            System.out.println(new String(table[i]));
        }
    }

    public static boolean check(char[][] table, int i, int j, int k) {
        // 检查同行和同列
        for (int l = 0 ; l < 9 ; l++) {
            if (table[i][l] == (char)('0' + k))
                return false;
            if (table[l][j] == (char)('0' + k))
                return false;
        }
        // 检查小九宫格
        for (int l = (i / 3) * 3 ; l < (i / 3 + 1) * 3 ; l++) {
            for (int m = (j / 3) * 3 ; m < (j / 3 + 1) * 3 ; m++) {
                if (table[l][m] == (char)('0' + k))
                    return false;
            }
        }
        return true;
    }
}
